package collection.list;

public class CircularArrayFIFOQueue implements Queue {
    /**
     * 环形数组大小上限
     */
    private static final int MAX_ARRAY_SIZE =65536;

    /**
     * 环形数组，存放队列元素
     */
    private Object[] items;

    private int queueSize;

    /**
     * 队列头部（在items中）的下标
     */
    private int front;

    /**
     * 队列尾部（在items中）的下标
     */
    private int rear;

    /**
     * 带参数的构造函数，输入参数为队列初始化的大小。此处约定队列长度不得超过初始化的长度。
     * 初始化时，rear应指向front的“前”一元素。
     *
     * @param initQueueSize 队列中最多可容纳的元素数量
     */
    public CircularArrayFIFOQueue(int initQueueSize) {
        if (initQueueSize<1 || initQueueSize>MAX_ARRAY_SIZE){
            throw new RuntimeException("队列大小最小为1，最大为"+MAX_ARRAY_SIZE);
        }
        //环形逻辑数组让第一个位置与最后一个位置重合，会牺牲一个位置，所以实际数组要加1
        queueSize = initQueueSize+1;
        items = new Object[queueSize];
        front = 0;
        rear = queueSize-1;
    }

    //…

    @Override
    public boolean enqueue(Object o) {
        if ( (rear+2) % queueSize == front ){  //队列已满
            return false;
        }
        rear = (rear+1) % items.length;
        items[rear] = o;
        return true;
    }

    @Override
    public Object dequeue() {
        if ( (rear+1) % queueSize == front ){  //队列为空
            return null;
        }
        return items[front++];
    }

    @Override
    public int size() {
        if ( (rear+1) % queueSize == front ){
            return 0;
        }
        if ( (rear+2) % queueSize == front ){
            return queueSize-1;
        }
        return rear-front+1;
    }

    public static void main(String[] args){
        Queue queue = new CircularArrayFIFOQueue(10);
        System.out.println(queue.size());
        for (int i=0; i<15; i++){
            System.out.println(queue.enqueue(i)+"\t"+queue.size());
        }
        for (int i=0; i<15; i++){
            System.out.println(queue.dequeue()+"\t"+queue.size());
        }
    }

}
